package com.base.dp;

import java.util.Arrays;

public class DeleteAndGet {
    public static void main(String[] args) {
        System.out.println(new DeleteAndGet().deleteAndEarn(new int[]{2, 2, 3, 3, 3, 4}));
    }

    /**
     * 给你一个整数数组 nums ，你可以对它进行一些操作。
     * <p>
     * 每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
     * <p>
     * 开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
     *
     * @param nums 输入
     * @return 结果
     */
    public int deleteAndEarn(int[] nums) {
        //排序：首先，可以对数组进行排序，这样相同的数字会聚集在一起，便于处理。

        int max = Arrays.stream(nums).max().getAsInt();
        //最大的是4，那么数组长度就是5,最大数是下标
        int[] numsCount = new int[max + 1];
        //统计每个数字的点数
        for (int num : nums) {
            numsCount[num] += num;
        }
        //初始化dp数组   数组长度是最大值加1，dp数组存的是从1到最大值直接，每个数字能获得的最大点数，而不是nums数组中，每个元素的最大点数，特别需要注意理解这点
        //也可以理解为排序数组 1到最大值，每个数字能获得的最大点数
        int[] dp = new int[max+1];

        //从1开始统计，可能没有1，那么就是0
        dp[1] = numsCount[1];
        for (int i = 2; i <= max; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + numsCount[i]);
        }
        return dp[max];
    }
}
